// https://leetcode.cn/problems/rectangle-area-ii/
// Created by ade on 2022/9/16.
//
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>

using namespace std;

class Solution {
public:
    // 思考：暴力法的时间和空间复杂度是O(N的N次方) 肯定是不行的
    unordered_map<int, vector<vector < int>> >
    res;

    // 这种转化为二维坐标的方式还是会超时
    int rectangleArea1(vector <vector<int>> &rectangles) {
        for (auto rect : rectangles) {
            transfer(rect);
        }
        for (auto &i : res) {
            sort(i.second.begin(), i.second.end(), [](vector<int> a, vector<int> b) {
                if (a[0] < b[0]) return true;
                else if (a[0] == b[0]) return a[1] <= b[1];
                return false;
            });
        }
        int sum = 0;
        for (auto &i : res) {
            vector<int> st = {i.second[0][0], i.second[0][1]};
            sum += st[1] - st[0];
            for (int j = 1; j < i.second.size(); j++) {
                if (i.second[j][0] <= st.back()) {
                    if (i.second[j][1] <= st.back()) {
                        continue;
                    } else {
                        sum += i.second[j][1] - st.back();
                        st[1] = i.second[j][1];
                    }
                } else {
                    st[0] = i.second[j][0];
                    st[1] = i.second[j][1];
                    sum += st[1] - st[0];
                }
            }
        }
        return sum;
    }

    // 转化坐标 0,0,2,2
    void transfer(vector<int> rect) {
        for (int i = rect[0]; i < rect[2]; i++) {
            vector<int> tmp = {rect[1], rect[3]};
            res[i].push_back(tmp);
        }
    }

    int rectangleArea(vector <vector<int>> &rectangles) {
        int sum = 0;
        sort(rectangles.begin(), rectangles.end(), [](vector<int> a, vector<int> b) {
            if (a[0] < b[0]) return true;
            else if (a[0] == b[0]) {
                if (a[1] <= b[1]) return true;
                return false;
            }
            return false;
        });
        for (auto &rect : rectangles) {
            cout << rect[0] << "," << rect[1] << "," << rect[2] << "," << rect[3] << endl;
        }
        return 0;

//        int len = rectangles.size();
//        int low = rectangles[0][0];
//        int high = rectangles[len - 1][3];
//        for (auto &rect : rectangles) {
//            if (rect[1] < low) low = rect[1];
//            if (rect[3] > high) high = rect[3];
//        }
//        for (int i = low; i < high; i++) {
//
//        }
    }


};

int main() {
    vector <vector<int>> rectangles = {
            {0, 0, 2, 2},
            {1, 0, 2, 3},
            {1, 0, 3, 1}
    };
    Solution so;
    cout << so.rectangleArea(rectangles);
    return 0;
}